/*
 * BinaryHeap.cpp
 *
 *  Created on: 2013-1-23
 *      Author: Administrator
 */

#include <iostream>
#include <exception>
#include "BinaryHeap.h"
using namespace std;

BinaryHeap::BinaryHeap(int capacity):_currentSize(0), _array(capacity, 0)
{
}

BinaryHeap::BinaryHeap(const std::vector<int>& items):_currentSize(items.size()), _array(items)
{
}

bool BinaryHeap::isEmpty() const
{
	return _array.size() == 1 ? true : false;
}

const int BinaryHeap::findMin() const
{
	return _array[1];
}

void BinaryHeap::print() const
{
	cout<<"Printing the Binary Heap"<<endl;
	for(unsigned iter = 1; iter <= _currentSize; ++iter)
	{
		cout<<_array[iter]<<" ";
	}
	cout<<endl;
}

void BinaryHeap::insert(int x)
{
	//overflow
	if(_array.size() -1 == _currentSize)
	{
		_array.resize(_array.size() * 2);
	}
	//Note: hole begins at the end of the heap
	unsigned hole = ++_currentSize;
	//percolate up the hole
	for(; hole > 1 && x < _array[hole / 2]; hole /= 2)
	{
		_array[hole] = _array[hole / 2];
	}
	//insert x into hole
	_array[hole] = x;
}

BinaryHeap::~BinaryHeap()
{
	// TODO Auto-generated destructor stub
}

int BinaryHeap::deleteMin()
{
	if(isEmpty())
	{
		return 0;
	}
	unsigned hole = 1;
	_array[hole] = _array[_currentSize--];
	percDown(hole);

	return 0;
}

void BinaryHeap::makeEmpty()
{
	_array.clear();
	_currentSize = 0;
}

void BinaryHeap::buildHeap()
{
	for(unsigned i = _currentSize / 2; i > 0; --i)
	{
		percDown(i);
	}
}

void BinaryHeap::percDown(unsigned hole)
{
	int temp = _array[hole];
	unsigned child ;
	for(; hole * 2 < _currentSize; hole = child)
	{
		child = hole * 2;
		if(child != _currentSize && _array[child] > _array[child+1])
		{
			++child;
		}
		if(_array[child] < temp)
		{
			_array[hole] = _array[child];
		}
		else break;
	}
	_array[hole] = temp;
}
